<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <style>

    </style>
</head>

<body>

</body>
<script>
    var array = [2, 3, 1, 6, 0, 43, 67, 164, 732, -4, -752, 2, 6834];

    // 1.冒泡排序
    // 冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元  素进行大小的比较，
    // 根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。
    function bubbleSort(arr) {
        for (let i = 0; i < arr.length - 1; i++) {//外层循环控制排序趟数
            for (let j = 0; j < arr.length - 1 - i; j++) {//内层循环控制每一趟排序多少次
                if (arr[j] > arr[j + 1]) {
                    let temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    // 2.选择排序
    // 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
    // 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
    function selectionSort(arr) {
        for (var i = 0; i < arr.length - 1; i++) {
            for (var j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    var temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
        return arr;
    }

    // 3.插入排序
    // 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
    function insertSort(data) {
        var len = data.length;
        for (var i = 1; i < len; i++) {
            var key = data[i];
            var j = i - 1;
            while (j >= 0 && data[j] > key) {
                data[j + 1] = data[j];
                j--;
            }
            data[j + 1] = key;
        }
        return data;
    }

    // 4.归并排序
    // 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
    // 若将两个有序表合并成一个有序表，称为2-路归并。它使用了递归分治的思想；
    // 相当于：左半边用尽，则取右半边元素；右半边用尽，则取左半边元素；右半边的当前元素小于左半边的当前元素，则取右半边元素；
    // 右半边的当前元素大于左半边的当前元素，则取左半边的元素。
    function mergeSort(array) {
        var len = array.length;
        if (len < 2) {
            return array;
        }
        var middle = Math.floor(len / 2),
            left = array.slice(0, middle),
            right = array.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }
    function merge(left, right) {
        var result = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        while (left.length)
            result.push(left.shift());
        while (right.length)
            result.push(right.shift());
        return result;
    }

    function digui(arr) {
        var len = arr.length;
        if (len < 2) return arr;
        var middle = Math.floor(len / 2);
        var left = arr.slice(0, middle);
        var right = arr.slice(middle);
        return merge(digui(left), digui(right));
    }
    function merge(left, right) {
        var res = [];
        while (left.length && right.length) {
            if (left[0] < right[0]) {
                res.push(left.shift())
            } else {
                res.push(right.shift())
            }
        }
        if (left.length) res.push(...left);
        if (right.length) res.push(...right);
        return res
    }
    console.log(digui([4, 2, 1, 3, 5, 6, 8, 0, 7]));

    // 5.快速排序
    // 通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，
    // 然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，
    // 最终能够实现将所需排序的无序序列元素变为一个有序的序列。
    function quickSort(arr) {
        if (arr.length <= 1) return arr;
        var left = [];
        var right = [];
        var pivot = arr[0];
        for (var i = 1; i < arr.length; i++) {
            if (arr[i] < pivot) {
                left.push(arr[i]);
            }
            else {
                right.push(arr[i])
            }
        }
        return quickSort(left).concat(pivot, quickSort(right));
    }
    console.log(quickSort([4, 2, 3, 4, 0, 5, 7, 3, 8]));

    // console.log(JSON.stringify({ a: 1, b: '1', c: null, d: undefined, e: false }));
</script>

</html>